package 递归or回溯;
import java.util.*;
/**
 * 生成数组的所有排列
 * 时间复杂度O(n!)，空间复杂度O(n)，n为数组长度
 */
public class permute {
    /**
     * 生成数组的所有排列
     * 
     * @param nums 输入数组
     * @return 所有排列的列表
     */
    public static List<List<Integer>> premuteM(int[] nums){
        back(nums); // 调用回溯方法生成排列
        return res; // 返回所有排列的列表
    }

    private static List<List<Integer>> res = new ArrayList<>(); // 用于存储所有排列
    private static List<Integer> path = new ArrayList<>(); // 用于存储当前路径

    /**
     * 回溯方法，用于生成排列
     * 
     * @param nums 输入数组
     */
    private static void back(int[] nums){
        if(path.size() == nums.length){ // 如果当前路径长度等于数组长度，表示生成了一个排列
            res.add(new ArrayList<>(path)); // 将当前路径加入结果列表
            return; // 返回
        }
        for(int num : nums){ // 遍历数组中的每个元素
            if(!path.contains(num)){ // 如果当前元素不在路径中
                path.add(num); // 将当前元素加入路径
                back(nums); // 递归生成排列
                path.remove(path.size() - 1); // 移除当前元素
            }
        }
    }

    /**
     * 主函数：处理输入输出
     * 输入格式：一行数字，用逗号分隔，表示输入数组
     * 例如：1,2,3 表示一个输入数组
     * 输出格式：所有排列的列表
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(","); // 读取输入并分割
        int[] nums = new int[s.length]; // 创建输入数组
        for(int i = 0; i < s.length; i++){ // 将输入转换为整数数组
            nums[i] = Integer.parseInt(s[i]); // 将字符串转换为整数
        }
        System.out.println(premuteM(nums)); // 输出所有排列
        sc.close(); // 关闭输入流
    }
}
